import java.util.EmptyStackException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * The LinkedStack class represents a last-in-first-out (LIFO) stack of objects,
 * based on linking elements in a way like LinkedList do that. Inner class Node
 * provide an opportunity to store elements linked. The usual push and pop
 * operations are provided, as well as a method to peek at the top item on the
 * stack,  a method to test for whether the stack is empty,  method to get size
 * of stack, and clear metod. When a stack is first created, it contains no items.
 *
 *   @author Leonid Ch.
 *   ITMO
 *   group 3514
 *
 */

public class LinkedStack<E> {

    private class LinkedNode<T> {
        private T item;
        private LinkedNode<T> next;


/** 
 * Linked Node - a class that represents the elements of the stack
 * Each object LinkedNode contains another object LinkedNode LinkedNode
 * until the moment when LinkedNode! = NULL
 * constructor to build a node with no successor
 * @param the value to be stored by this node
*/


        private LinkedNode(T value, LinkedNode<T> reference) {
            item = value;
            next = reference;
        }
    }
    
/** 
 * constructor to build a node with a specified (perhaps null) successor
 * @param the value to be stored by this node
 * @param the next field for this node
*/

    private LinkedNode<E> top; // vertex of the stack
    private int size = 0;


    public LinkedStack() {
        top = null;             // empty stack
    }
    
/**
 * no-arguments default constructor creates an empty stack
*/

    public boolean empty() {
        return (top == null);
    }
    
/**
 * @return	whether the stack is empty
*/


    public void push(E value) {
        top = new LinkedNode<E>(value, top);
        size++;
    }
    
/** 
 *@param	value to push onto the stack
*/

    public E pop() throws EmptyStackException {
        if (empty()) {
            throw new EmptyStackException();
        }
        E result = top.item;
        top.item = null;
        top = top.next;
        size--;
        return result;
    }

/** 
 *@return	the top value on the stack
*/

    public E peek() throws EmptyStackException {
        if (empty()) {
            throw new EmptyStackException();
        }
        return top.item;
    }
/**
*@return	the top value on the stack
*/

    public int size() {
        return size;
    }

    public void clear() {
        try {
            for (; pop() != null; ) ;
        } catch (EmptyStackException e) {
        }
    }

    public String toString() {
        Iterator<E> i = new LinkedStackIterator(top);
        if (!i.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (; ; ) {
            E e = i.next();
            sb.append(e);
            if (!i.hasNext())
                return sb.append(']').toString();
            sb.append(", ");
        }
    }

/** convert the stack to a printable string
 * @return	a string representing the stack
     */

    private class LinkedStackIterator<E> implements Iterator<E> {

        private LinkedNode<E> cur;

        private LinkedStackIterator(LinkedNode<E> top) {
            cur = top;
        }
        
/**
 * Represents stack as a <code>String</code>
 *
 * @return String, containing all elements of stack in order.
*/

        @Override
        public boolean hasNext() {
            return cur != null;
        }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E item = cur.item;
            cur = cur.next;
            return item;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    public static void main(String[] args) {
        LinkedStack<String> stringLinkedStack = new LinkedStack<String>();

        System.out.println("before pushing anything, " + stringLinkedStack.toString() + ", must be []");
        stringLinkedStack.push("Leo");
        stringLinkedStack.push("Che");
        stringLinkedStack.push("Ho");
        System.out.println("after pushing Leo, Che and Ho: " + stringLinkedStack.toString() + ", must be [Ho, Che, Leo]");
        System.out.println("size: " + stringLinkedStack.size() + ", must be 3");
        System.out.println("pop returns: " + stringLinkedStack.pop() + ", must be Ho");
        System.out.println("after popping, " + stringLinkedStack.toString() + ", must be [Che, Leo]");
        stringLinkedStack.push("Ch");
        stringLinkedStack.push("G");
        stringLinkedStack.push("Leonid");
        System.out.println("after pushing Ch, G and Leonid: " + stringLinkedStack.toString() + ", must be [Leonid, G, Ch, Che, Leo]");
        System.out.println("size: " + stringLinkedStack.size() + ", must be 5");
        System.out.println("pop returns: " + stringLinkedStack.pop());
        System.out.println("size: " + stringLinkedStack.size() + ", must be 4");
        System.out.println("pop returns: " + stringLinkedStack.pop());
        System.out.println("size: " + stringLinkedStack.size() + ", must be 3");
        System.out.println("pop returns: " + stringLinkedStack.pop());
        System.out.println("pop returns: " + stringLinkedStack.pop());
        System.out.println("after popping: " + stringLinkedStack.toString() + ", must be [Leo]");

/** 
is a simple test program that checks each of our method
*/


        LinkedStack<Integer> integerLinkedStack = new LinkedStack<Integer>();
        for (int i = 1; i <= 100; i++) {
            integerLinkedStack.push(i);
        }

        System.out.println("size: " + integerLinkedStack.size() + ", must be 100");
        for (int i = 100; i > 10; i--) {
            Integer returned = integerLinkedStack.pop();
            if (!returned.equals(i)) {
                System.out.println("error: pop returns " + returned + ", expected " + i);
            }
        }

        System.out.println("size: " + integerLinkedStack.size() + ", must be 10");
        integerLinkedStack.clear();
        System.out.println("size: " + integerLinkedStack.size() + ", must be 0");
    }
}

/** 
output values are based on tests
*/
